package 极客算法训练营.chapter09;

import java.util.*;
import java.util.stream.Collectors;

public class 单词接龙2 {

    class Solution {
        private int minDistance = Integer.MAX_VALUE;
        private List<List<String>> ans = new ArrayList<>();
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Set<String> wordSet = new HashSet<>(wordList);
            Set<String> visited = new HashSet<>();
            Deque<String> path = new ArrayDeque<>();
            path.addLast(beginWord);
            visited.add(beginWord);
            dfs(beginWord, endWord, path, wordSet, visited);
            return ans.stream().filter(e -> e.size() == minDistance).collect(Collectors.toList());
        }

        public void dfs(String curWord, String endWord, Deque<String> path, Set<String> wordSet, Set<String> visited) {
            if (curWord.equals(endWord)) {
                minDistance = Math.min(minDistance, path.size());
                ans.add(new ArrayList<>(path));
                return;
            }
            for (String word : wordSet) {
                if (!visited.contains(word) && chageDiff(curWord, word) == 1) {
                    path.addLast(word);
                    visited.add(word);
                    dfs(word, endWord, path, wordSet, visited);
                    visited.remove(word);
                    path.removeLast();
                }
            }
        }

        private int chageDiff(String curWord, String word) {
            int diff = 0;
            char[] s1 = curWord.toCharArray();
            char[] s2 = word.toCharArray();
            for (int i = 0; i < s1.length; i++) {
                if (s1[i] != s2[i]) {
                    diff++;
                }
            }
            return diff;
        }
    }

    class SolutionUP {
        private int minDistance = Integer.MAX_VALUE;

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            char[] begin = beginWord.toCharArray();
            char[] end = endWord.toCharArray();
            char[][] wordListArray = new char[wordList.size()][];
            for (int i = 0; i < wordList.size(); i++) {
                wordListArray[i] = wordList.get(i).toCharArray();
            }
            List<List<String>> ans = new ArrayList<>();
            Deque<String> path = new ArrayDeque<>();
            path.add(beginWord);
            dfs(begin, end, wordListArray, path, ans);
            return ans.stream().filter((e) -> e.size() == minDistance).collect(Collectors.toList());
        }

        public void dfs(char[] begin, char[] end, char[][] wordListArray, Deque<String> path, List<List<String>> ans) {
            if (Arrays.equals(begin, end)) {
                ans.add(new ArrayList<>(path));
                minDistance = Math.min(minDistance, path.size());
                return;
            }

            for (int i = 0; i < wordListArray.length; i++) {
                char[] word = wordListArray[i];
                if (word == null) continue;
                int diff = 0;
                for (int j = 0; j < word.length; j++) {
                    if (begin[j] != word[j]) {
                        diff++;
                    }
                }
                if (diff == 1) {
                    wordListArray[i] = null;
                    path.addLast(new String(word));
                    dfs(word, end, wordListArray, path, ans);
                    path.removeLast();
                    wordListArray[i] = word;
                }
            }
        }
    }
}
